A 3-dimensional computer graphics environment, such as an interactive walk-through virtual environment, may include millions of triangles. Processing of such graphics data for display is computationally intensive. In many situations, only a relatively small portion of an environment is visible to a user at a given time. Thus, algorithms have been developed to cull triangles that not visible to the user, to reduce the amount of data sent to a graphics pipeline. Culling techniques include view frustum culling and occlusion culling.
View frustum culling is a technique where only triangles contained in a current view frustum are sent to a graphics pipeline.
Occlusion culling techniques seek to identify and cull triangles that are occluded behind other triangles. Occlusion culling techniques include view point and region based techniques.
View point techniques seek to identify occluded triangles with respect to a current view point, or virtual position of a user. View point based visibility tests are re-computed for every frame.
Region based techniques seek to identify occluded triangles with respect to a range of view points, or a view cell. Region based techniques seek to exploit spatial coherence within visible geometry for proximate viewpoints, and temporal coherence of user movement, to amortize costs of visibility culling over multiple frames. Once computed, a visible set is valid until a user moves out of the view cell.
Region based techniques include orthographic projection to project objects onto a bitmap coincident with a ground plane, and thus referred to as rendering in 2.5-dimensions. Orthographic projection involves storing of substantial geometry of rendered objects.
In the drawings, the leftmost digit(s) of a reference number identifies the drawing in which the reference number first appears.